package com.lz.learning.dp;

import java.util.Arrays;

public class DPDemo {
    public static void main(String[] args) {

        DPDemo dpDemo = new DPDemo();
        dpDemo.maxChildSequence(new int[]{10, 9, 2, 5, 3, 7, 101});
    }

    /**
     * 递增子序列
     * <p>
     * {10,9,2,5,3,7,101}
     * <p>
     * 2 3 7 101 -> 4
     * <p>
     * 复杂度O(n^2)
     * 扑克牌的方式 nlogN
     *
     * @param array
     * @return
     */
    int maxChildSequence(int[] array) {
        if (array.length < 1) return 0;
        // 后一个数比前一个数大
        int[] dp = new int[array.length];
        Arrays.fill(dp, 1);

        int max = -1;
        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < i; j++) {
                if (array[i] > array[j]) {
                    dp[i] = (dp[j] + 1);
                    max = max > dp[i] ? max : dp[i];
                }

            }
        }
        System.out.println(max);
        return max;
    }
}
